In this paper, we focus on the problem of determining whether two conjunctive("CQ") queries posed on relational data are combined-semantics equivalent [9].We continue the tradition of [2,5,9] of studying this problem using the tool ofcontainment between queries. We introduce a syntactic necessary and sufficientcondition for equivalence of queries belonging to a large natural language of"explicit-wave" combined-semantics CQ queries; this language encompasses (butis not limited to) all set, bag, and bag-set queries, and appears to cover allcombined-semantics CQ queries that are expressible in SQL. Our result solves inthe positive the decidability problem of determining combined-semanticsequivalence for pairs of explicit-wave CQ queries. That is, for an arbitrarypair of combined-semantics CQ queries, it is decidable (i) to determine whethereach of the queries is explicit wave, and (ii) to determine, in case bothqueries are explicit wave, whether or not they are combined-semanticsequivalent, by using our syntactic criterion. (The problem of determiningequivalence for general combined-semantics CQ queries remains open. Even so,our syntactic sufficient containment condition could still be used to determinethat two general CQ queries are combined-semantics equivalent.) Our equivalencetest, as well as our general sufficient condition for containment ofcombined-semantics CQ queries, reduce correctly to the special cases reportedin [2,5] for set, bag, and bag-set semantics. Our containment and equivalenceconditions also properly generalize the results of [9], provided that thelatter are restricted to the language of (combined-semantics) CQ queries.
展开▼
